package main.java.learning.directory.Work.排序.Ac;

/**
 * @author aichao
 * @date 2021/2/19
 */
public class QuickSortDay2 {
    public static void main(String[] args) {
        int[] arrQuickSort = {49, 38, 65, 97, 23, 22, 76, 1};
        quickSort(arrQuickSort, 0, arrQuickSort.length - 1);
        for (int i : arrQuickSort) {
            System.out.println(i + "\t");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //待排序列起始位置
        int leftIndex = left;
        //待排序列结束位置
        int rightIndex = right;
        //基准值
        int key = arr[left];

        //从左右两边交替扫描，直到left = right
        while (leftIndex < rightIndex) {
            //从右往左扫描，找到第一个比基准值小的元素
            while (rightIndex > leftIndex && arr[rightIndex] >= key) {
                rightIndex--;
            }
            //比基准值小的元素放左边
            arr[leftIndex] = arr[rightIndex];

            //从左往右扫描，找到第一个比基准值大的元素
            while (leftIndex < rightIndex && arr[leftIndex] <= key) {
                leftIndex++;
            }
            //比基准值大的元素放右边
            arr[rightIndex] = arr[leftIndex];
        }
        //基准值归位
        arr[leftIndex] = key;
        //对基准值左边的元素继续递归调用排序
        quickSort(arr, left, leftIndex - 1);
        //对基准值右边的元素继续递归调用排序
        quickSort(arr, rightIndex + 1, right);
    }
}
